package tree;

public class Heap {

	public static void main(String[] args) throws InterruptedException {
		
		Heap heap = new Heap();
		
		heap.Insert(1);
		heap.Insert(2);
		heap.Insert(3);
		heap.Insert(3);
		heap.Insert(5);
		heap.Insert(3);
		heap.Insert(6);
		heap.Delete();
		heap.Delete();
		heap.Delete();

		printHeap(heap);
	}

	private static <E> void printHeap(Heap heap) {
		E[] array = (E[])heap.getItemArray();
		for(E i : array)
		{
			System.out.print(i + " ");
		}
		System.out.println();
	}
	
	private int count = 0;
	private int capacity = 20;
	private Integer[] itemArray;
	
	@SuppressWarnings("unchecked")
	public Heap()
	{
		itemArray = new Integer[capacity];
		for(int i=0; i<itemArray.length; i++)
		{
			itemArray[i] = 0;
		}
	}

	@SuppressWarnings({ "unchecked", "rawtypes" })
	public void Insert(Integer item)
	{
		itemArray[count] = item;
		//p-up
		int i = count;
		// parentPos = (childPos - 1) / 2
		while(i>0 &&  item > itemArray[(i-1)/2])
		{
			// swap with parent if parent is smaller
			Integer temp = itemArray[i];
			itemArray[i] = itemArray[(i-1)/2];
			itemArray[(i-1)/2] = temp;
			i = (i-1)/2;
		}
		count++;
		printHeap(this);
	}
	
	public Integer Delete() throws InterruptedException
	{
		if(count == 0)
		{
			return null;
		}
		Integer result = itemArray[0];
		// swap first element with last and then p-d
		System.out.println("Swapping first and last pos" + (count -1));
		itemArray[0] = itemArray[count-1];
		// null out the last
		itemArray[count-1] = 0; 
		printHeap(this);
		
		//p-down
		int i = 0; // start at begining
		while(i < count-1)
		{
			int leftChildPos = i * 2 + 1;
			int rightChildPos = i * 2 + 2;
			Thread.sleep(1000);
			int largerChildPos = (itemArray[leftChildPos] > itemArray[rightChildPos]) ? leftChildPos : rightChildPos;
			if(itemArray[i] < itemArray[largerChildPos])
			{
				System.out.println("Swapping pos" + i + " and pos" + largerChildPos);
				Integer temp = itemArray[i];
				itemArray[i] = itemArray[largerChildPos];
				itemArray[largerChildPos] = temp;
				i = largerChildPos;
				printHeap(this);
			}
			else
			{
				break;
			}
		}
		count--;
		return result;
	}
	
	public Integer[] getItemArray()
	{
		return itemArray;
	}
}
